package cn.hycat.leetcode.middle;

import java.util.*;

/**
 * @author 吕泽浩业
 * @version 1.0
 */

/**     优先队列 + 大根堆 + 哈希表
 *
 */
public class L692前K个高频单词 {
    class Node {
        public String key;
        public int value;
        public Node(String key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap();
        for(int i = 0; i < words.length; i++) {
            if(map.get(words[i])==null)
                map.put(words[i], 1);
            else
                map.put(words[i], map.get(words[i]) + 1);
        }

        PriorityQueue<Node> heap = new PriorityQueue(new Comparator<Node>() {
            @Override
            public int compare(Node a, Node b) {
                if (a.value != b.value) return b.value - a.value;
                return a.key.compareTo(b.key);
            }
        });

        for(String s : map.keySet()) {
            heap.add(new Node(s, map.get(s)));
        }

        List<String> ansList = new ArrayList();
        while(k-- > 0) {
            Node node = heap.poll();
            ansList.add(node.key);
        }
        return ansList;
    }

}
